from heapq import heapify, heappop
from copy import copy


class Dijkstra:
    def __init__(self, Zero, Infinity):
        self.Zero = Zero
        self.Infinity = Infinity

    def __extract_min(self, Q):
        heapify(Q)
        return heappop(Q)

    def dijkstra (self, G, w, s):
        S = {} # Store distances between s and the other graph vertices
        P = {} # Keeps all the ancestors of vertices in graph G
        for r in G.vertices:
            r.key = self.Infinity
            P[r] = None
        s.key = self.Zero
        Q = copy(G.vertices)
        while len(Q) != 0:
            u = self.__extract_min(Q)
            for r in G.adjacencies(u):
                if r.key > u.key + w((u, r)):
                    r.key = u.key + w((u, r))
                    P[r] = u
            t = u
            path = [t]
            while P[t] is not None:
                path.append(P[t])
                t = P[t]
            S[u] = path
        return S
